/**
 * 剑指 Offer 56 - II. 数组中数字出现的次数 II
 * https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
 */
public class Solutions_Offer_56_II {
    public static void main(String[] args) {
//        int[] nums = {3, 4, 3, 3};  // output: 4
//        int[] nums = {9, 1, 7, 9, 7, 9, 7};  // output: 1
        int[] nums = {9, 17, 7, 9, 7, 9, 7};  // output: 17

        int result = singleNumber(nums);
        System.out.println(result);
    }

    public static int singleNumber(int[] nums) {
        int res = 0;
        // bitMap[31] = 4：表示 nums 中全部元素在第 31 位上（从 0 开始，从左往右）有 4 个 bit 位 1
        int[] bitMap = new int[32];

        /**
         * nums = {3, 3, 4, 3}, 4(0b0100), 3(0b0011)
         *  27 28 29 30 31
         *   0  0  1  3  3
         */
        // 逐位统计
        for (int num : nums) {
            int index = bitMap.length - 1;
            // nums 都是大于等于 1 的数，故而判断条件可以写 大于 0
            while (num > 0) {
                bitMap[index--] += num & 1;
                num = num >> 1;
            }
        }
        for (int i = bitMap.length - 1; i >= 0; i--) {
            int count = bitMap[i] % 3;
            if (count != 0) {
                // 不能被 3 整除的位上，即表示只出现一次的数字有 bit位 1 在该位上
                res += 1 << (31 - i);
            }
        }
        return res;
    }
}
